/**
 * 
 */
package backtrack.passed2;

/**
 * @author xyyi
 *
 */
public class WordSearch {

	/**
	Given a 2D board and a word, find if the word exists in the grid.

	The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

	For example,
	Given board =

	[
	  ["ABCE"],
	  ["SFCS"],
	  ["ADEE"]
	]
	word = "ABCCED", -> returns true,
	word = "SEE", -> returns true,
	word = "ABCB", -> returns false.
	 */
	// Good for interview
    public boolean exist(char[][] board, String word) {
        if (board == null || word == null)
            return false;

        int rows = board.length, cols = board[0].length;
        final boolean[][] flags = new boolean[rows][cols]; {
            for (int row = 0; row < rows; row++) {
                for (int col = 0; col < cols; col++) {
                    boolean result = existHelper(row, col, board, flags, 0, word);
                    if (result)
                       return result;
                }
            }
        }
        
        return false;
    }
    
    private boolean existHelper(int row, int col, char[][] board, boolean[][] flags, int wordIdx, String word) {
        int rows = board.length, cols = board[0].length;
        
        if (wordIdx == word.length())
            return true;
        if (row == -1 || row == rows || col == -1 || col == cols)
            return false;
        if (flags[row][col])
            return false;

        if (board[row][col] == word.charAt(wordIdx)) {
            flags[row][col] = true;
            int[] moveRow = {-1, 0, 1, 0};
            int[] moveCol = {0, 1, 0, -1};
            for (int i = 0; i < 4; i++) {
                boolean isExisted = existHelper(row + moveRow[i], col + moveCol[i], board, flags, wordIdx + 1, word);
                if (isExisted)
                    return isExisted;
            } 
            flags[row][col] = false;
        }

        return false;        
    }	
	
	public boolean existR2(char[][] board, String word) {

		int rows = board.length;
		int cols = board[0].length;
		boolean[][] flags = new boolean[rows][cols];
		StringBuilder sb = new StringBuilder();
		for (int row = 0; row < rows; row++) {
			for (int col = 0; col < cols; col++) {
				boolean result = existeR2Helper(row, col, flags, sb, board, word);
				if (result) {
					return result;
				}
				sb.setLength(0);
			}
		}

		return false;
	}

	private boolean existeR2Helper(int row, int col, boolean[][] flags,
			StringBuilder sb, char[][] board, String word) {
		int rows = board.length;
		int cols = board[0].length;

		if (row == -1 || col == -1 || row == rows || col == cols)
			return false;
		if (flags[row][col])
			return false;
		if (board[row][col] != word.charAt(sb.length()))
			return false;

		flags[row][col] = true;
		sb.append(board[row][col]);
		if (word.equals(sb.toString()))
			return true;

		boolean result = existeR2Helper(row - 1, col, flags, sb, board, word); // top
		if (result) {
			return result;
		}
		result = existeR2Helper(row, col + 1, flags, sb, board, word); // left
		if (result) {
			return result;
		}
		result = existeR2Helper(row + 1, col, flags, sb, board, word);// bottom
		if (result) {
			return result;
		}
		result = existeR2Helper(row, col - 1, flags, sb, board, word);// right
		if (result) {
			return result;
		}

		flags[row][col] = false;
		sb.setLength(sb.length() - 1);
		return false;
	}

	/**
	 * 
	 */
	public WordSearch() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		WordSearch ws = new WordSearch();
		char[][] board = { { 'a', 'b', 'c', 'e' }, { 's', 'f', 'c', 's' },
				{ 'a', 'd', 'e', 'e' } };
		String word = "a";
		boolean result = ws.exist(board, word);

	}
}
